class Solution
{
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root)
    {
        if (root == nullptr) return true;
        bool left = isValidBST(root->left);
        if (left == false) return false;
        if (prev >= root->val) return false;
        prev = root->val;
        bool right = isValidBST(root->right);
        if (right == false) return false;
        return true;
    }
};
class Solution {
public:
    TreeNode* _sortedArrayToBST(vector<int>& nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* newnode = new TreeNode(nums[mid]);
        newnode->left = _sortedArrayToBST(nums, left, mid - 1);
        newnode->right = _sortedArrayToBST(nums, mid + 1, right);
        return newnode;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        return _sortedArrayToBST(nums, 0, nums.size() - 1);
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        if (root == nullptr) return {};
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            while (sz--)
            {
                TreeNode* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};
class Solution {
public:
    int MAX = 0;
    int GetHeight(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int left = GetHeight(root->left);
        int right = GetHeight(root->right);
        MAX = max(MAX, left + right);
        return left > right ? left + 1 : right + 1;
    }
    int diameterOfBinaryTree(TreeNode* root)
    {
        int left = GetHeight(root->left);
        int right = GetHeight(root->right);
        return max(MAX, left + right);
    }
};
class Solution {
public:
    bool isSymmetric(TreeNode* root)
    {
        return _isSymmetric(root->left, root->right);
    }
    bool _isSymmetric(TreeNode* left, TreeNode* right)
    {
        if (!left && !right) return true;
        if (!left || !right) return false;
        if (left->val != right->val) return false;
        return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
    }
};
class Solution {
public:
    TreeNode* invertTree(TreeNode* root)
    {
        if (root == nullptr) return nullptr;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        root->left = invertTree(right);
        root->right = invertTree(left);
        return root;
    }
};
class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);

        return left > right ? left + 1 : right + 1;
    }
};
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root)
    {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> ret;

        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            ret.push_back(top->val);
            cur = top->right;
        }
        return ret;
    }
};